{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# schedule_requests_sat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/sat/schedule_requests_sat.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/ortools/sat/samples/schedule_requests_sat.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "Nurse scheduling problem with shift requests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Union\n",
    "\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "def main() -> None:\n",
    "    # This program tries to find an optimal assignment of nurses to shifts\n",
    "    # (3 shifts per day, for 7 days), subject to some constraints (see below).\n",
    "    # Each nurse can request to be assigned to specific shifts.\n",
    "    # The optimal assignment maximizes the number of fulfilled shift requests.\n",
    "    num_nurses = 5\n",
    "    num_shifts = 3\n",
    "    num_days = 7\n",
    "    all_nurses = range(num_nurses)\n",
    "    all_shifts = range(num_shifts)\n",
    "    all_days = range(num_days)\n",
    "    shift_requests = [\n",
    "        [[0, 0, 1], [0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 1]],\n",
    "        [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 0], [1, 0, 0], [0, 0, 0], [0, 0, 1]],\n",
    "        [[0, 1, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0], [0, 1, 0], [0, 0, 0]],\n",
    "        [[0, 0, 1], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 0, 0]],\n",
    "        [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 0]],\n",
    "    ]\n",
    "\n",
    "    # Creates the model.\n",
    "    model = cp_model.CpModel()\n",
    "\n",
    "    # Creates shift variables.\n",
    "    # shifts[(n, d, s)]: nurse 'n' works shift 's' on day 'd'.\n",
    "    shifts = {}\n",
    "    for n in all_nurses:\n",
    "        for d in all_days:\n",
    "            for s in all_shifts:\n",
    "                shifts[(n, d, s)] = model.new_bool_var(f\"shift_n{n}_d{d}_s{s}\")\n",
    "\n",
    "    # Each shift is assigned to exactly one nurse in .\n",
    "    for d in all_days:\n",
    "        for s in all_shifts:\n",
    "            model.add_exactly_one(shifts[(n, d, s)] for n in all_nurses)\n",
    "\n",
    "    # Each nurse works at most one shift per day.\n",
    "    for n in all_nurses:\n",
    "        for d in all_days:\n",
    "            model.add_at_most_one(shifts[(n, d, s)] for s in all_shifts)\n",
    "\n",
    "    # Try to distribute the shifts evenly, so that each nurse works\n",
    "    # min_shifts_per_nurse shifts. If this is not possible, because the total\n",
    "    # number of shifts is not divisible by the number of nurses, some nurses will\n",
    "    # be assigned one more shift.\n",
    "    min_shifts_per_nurse = (num_shifts * num_days) // num_nurses\n",
    "    if num_shifts * num_days % num_nurses == 0:\n",
    "        max_shifts_per_nurse = min_shifts_per_nurse\n",
    "    else:\n",
    "        max_shifts_per_nurse = min_shifts_per_nurse + 1\n",
    "    for n in all_nurses:\n",
    "        num_shifts_worked: Union[cp_model.LinearExpr, int] = 0\n",
    "        for d in all_days:\n",
    "            for s in all_shifts:\n",
    "                num_shifts_worked += shifts[(n, d, s)]\n",
    "        model.add(min_shifts_per_nurse <= num_shifts_worked)\n",
    "        model.add(num_shifts_worked <= max_shifts_per_nurse)\n",
    "\n",
    "    model.maximize(\n",
    "        sum(\n",
    "            shift_requests[n][d][s] * shifts[(n, d, s)]\n",
    "            for n in all_nurses\n",
    "            for d in all_days\n",
    "            for s in all_shifts\n",
    "        )\n",
    "    )\n",
    "\n",
    "    # Creates the solver and solve.\n",
    "    solver = cp_model.CpSolver()\n",
    "    status = solver.solve(model)\n",
    "\n",
    "    if status == cp_model.OPTIMAL:\n",
    "        print(\"Solution:\")\n",
    "        for d in all_days:\n",
    "            print(\"Day\", d)\n",
    "            for n in all_nurses:\n",
    "                for s in all_shifts:\n",
    "                    if solver.value(shifts[(n, d, s)]) == 1:\n",
    "                        if shift_requests[n][d][s] == 1:\n",
    "                            print(\"Nurse\", n, \"works shift\", s, \"(requested).\")\n",
    "                        else:\n",
    "                            print(\"Nurse\", n, \"works shift\", s, \"(not requested).\")\n",
    "            print()\n",
    "        print(\n",
    "            f\"Number of shift requests met = {solver.objective_value}\",\n",
    "            f\"(out of {num_nurses * min_shifts_per_nurse})\",\n",
    "        )\n",
    "    else:\n",
    "        print(\"No optimal solution found !\")\n",
    "\n",
    "    # Statistics.\n",
    "    print(\"\\nStatistics\")\n",
    "    print(f\"  - conflicts: {solver.num_conflicts}\")\n",
    "    print(f\"  - branches : {solver.num_branches}\")\n",
    "    print(f\"  - wall time: {solver.wall_time}s\")\n",
    "\n",
    "\n",
    "main()\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
